Quadratic Arithmetic Programs: from Zero to Hero | by Vitalik Buterin
日本語補足
zkp とは、「ある主張を、根拠となるデータを明らかにせずに証明するもの」
コンピューターが実行できる形の主張
あるプログラムをある引数を与えて実行するとある結果になる
プログラムを算術回路 -> R1CS -> QAP -> 多項式と変換していく 回路のゲートごとに R1CS が定義でき、ゲートの数だけベクターのセットが存在する
プログラムを二項演算だけで表現する。Flattening。
フラットにしたプログラムに出てくる変数、引数、ダミー変数を1つのベクタにする。
R1CS とは、そのベクタがある条件を満たすような構造である
フラットにしたプログラム
code:flat
sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 + 5
これをベクタで表現する
ベクタはプログラム内のすべての変数とダミー変数、input、output から成る
こんな感じ
code:vector
記事の例にある変数を明示するとこのようになる
code:vector
これに実際の値を入れると
code:vector
このベクタから R1CS をつくる
R1CS は3つのベクタのセットからなり、Vectors A * Vectors B = Vectors C と定義される
1つの R1CS は1つの回路のゲートに対応する
例えば最初のゲート x * x = sym_1 を表現するには、input x = 3 とすると以下通り表現できる
code:Vectors A
Zipped result -> 3
code:Vectors B
Zipped result -> 3
code:Vectors C
Zipped result should be 9, because 3*3 is 9
code:R1CS for first gate
A * B = 3 * 3 = 9 = C
つまりこれらのベクタは、数式 x * x を評価していると考えることができる
Vectors A * Vecotors B = Vectors C が成り立つのであれば、x * x = sym_1 が成り立っている
2つ目のゲート sym_1 * x = y を表現すると以下
code:Vectors A
sym_1 is 9
code:Vectors B
x is 3
code:Vectors C
Zipped resultshould be 27, because 9*3 is 27
code:R1CS for second gate
A * B = 9 * 3 = 27 = C
3つ目のゲート sym_2 = y + x を表現すると以下
和を表現する必要がある。和はは Vectors A の中で表現し、Vecotors B を 1 とすることで Vectors A * Vectors B = Vectors C の定義内で和を表現する
code:Vectors A
Zipped result is 3 + 27 = 30
This is same as y + x = sym_2
code:Vectors B
Zipped result -> 1
code:Vectors C
Zipped resultshould be 30
code:R1CS for second gate
A * B = 30 * 1 = 30 = C
このようにして作成される R1CS を多項式に変換する
記事の例だと R1CS はこんな感じ
code:R1CS
A
B
C
Vector A の多項式 i を x = j について解くと、j番目のゲートの R1CS の Vector A の i 番目の要素になる
Vector A のすべての多項式を x = 1 について解くと、最初のゲートの R1CS の Vector A になる
多項式 i を x = 1, 2 ... について解いていくとグラフがかけるわけだが、そのグラフは、各ゲートの Vector A の i 番目の要素ということになる?
Vector A の多項式 1 を x = 1 について解いたときの y は、最初のゲートの Vector A の最初の要素。この例では 0 である
多項式 1 の期待する結果まとめ
code:results
(1,0)
(2,0)
(3,0)
(4,5)
多項式 0.833 * x**3 — 5*x**2 + 9.166*x - 5 になっていることが確認できる
Vector B の多項式1
整理すると、プログラムはゲートの連続で定義され、R1CS を使うことで、ある input が与えられたときのゲートの結果の正しさを確認できる。ある input とプログラムの実行結果が与えられたときに、すべての R1CS が満たされればすべてのゲートが正しく計算されたことが証明でき、すわなちプログラムが正しく実行されたことが証明できる。
R1CS はベクタの要素の和とその積によって確認できる
ベクタの要素を多項式で置き換えたことで、多項式の和と積によって R1CS の成立を確認できるようになった
多項式の和と積は一つの多項式に集約することができる
その多項式をすべての x (x=1 はゲート1, x=2 はゲート2であったことを思い出す)について解き、それが 0 であった場合、すべてのゲートの R1CS の成立を確かめたことと同じ意味をもつ
ベクタの要素を導くような多項式を定義できれば、多項式を解くことでベクタを作り出すことができる
多項式 A1 を x =1 についてとくと、ゲート1 のベクタAの1番目の要素が得られる、みたいな。
ラグランジュ補間を用いると、任意の座標を通る多項式をもとめることができるらしい
x=1 のとき、ゲート1のベクタAの1番目の要素、x=2 のとき、ゲート2のベクタAの1番目の要素、、、を導くような多項式があればよい
これは今回の例で言いかえると、(x, y) = (1, 0), (2, 0), (3, 0), (4, 5) を通るような多項式である
ラグランジュ補間を適用できることがわかる
1つの多項式に集約したとして、その多項式が常に0でなければならないわけではない。ゲートに対応する座標において0であればよい
これを確かめるには?
ゲートに対応するすべての座標において0になる多項式Zをもちいる
ある多項式がこの多項式Zの倍数であれば、Zと同じくゲートに対応するすべての座標において0になる